#include<iostream>
#include<queue>
using namespace std;

template<class T>
struct treeNode
{
    T element;
    treeNode*leftChild;
    treeNode*rightChild;
    treeNode(){
        leftChild=rightChild=nullptr;
    };
    treeNode(T&e){
        this->element=e;
        leftChild=rightChild=nullptr;
    }
};

//普通二叉树
template<class T>
class binaryTree{
private:
    int treeSize;
    treeNode<T>*root;
    void visit(treeNode<T>*node){
        if(node!=nullptr)
            cout<<"Node value is: "<<node->element<<endl;
        else
            cout<<"The node is nullptr."<<endl;
    }
public:
    binaryTree(){
        treeSize=0;
        root=nullptr;
    }
    ~binaryTree(){
        erase(root);
        root=nullptr;
        treeSize=0;
    }

    /*
    注意如下写法：
    treeNode<T>* getRoot(){
        return root;
    }
    在实际运行时，遇到root赋值语句报错：lvalue required as left operand of assignment
    此种写法返回的为复制值，并非实际指针
    */
    treeNode<T>*& getRoot(){
        return root;
    }
    bool isEmpty(){
        return this->treeSize==0;
    }
    int getSize(){
        return this->treeSize;
    }
    void preOrder(treeNode<T>*n);//前序遍历
    void inOrder(treeNode<T>*n);//中序遍历
    void postOrder(treeNode<T>*n);//后序遍历
    void levelOrder(treeNode<T>*n);//层次遍历
    void erase(treeNode<T>*n);//清空此二叉树
    int calHeight(treeNode<T>*n);//计算树高
};

template<class T>
void binaryTree<T>::preOrder(treeNode<T>*node){
    //前序遍历，中-左-右
    if(node!=nullptr){
        this->visit(node);
        preOrder(node->leftChild);
        preOrder(node->rightChild);
    }
}

template<class T>
void binaryTree<T>::inOrder(treeNode<T>*node){
    //中序遍历，左-中-右
    if(node!=nullptr){
        inOrder(node->leftChild);
        this->visit(node);
        inOrder(node->rightChild);
    }  
}

template<class T>
void binaryTree<T>::postOrder(treeNode<T>*node){
    //后序遍历，左-右-中
    if(node!=nullptr){
        inOrder(node->leftChild);
        inOrder(node->rightChild);
        this->visit(node);
    } 
}

template<class T>
void binaryTree<T>::levelOrder(treeNode<T>*node){
    //层次遍历
    queue<treeNode<T>*>q;//用于输出的队列
    while(node!=nullptr){
        this->visit(node);

        if(node->leftChild!=nullptr)
            q.push(node->leftChild);
        if(node->rightChild!=nullptr)
            q.push(node->rightChild);  

        if(q.empty())
            return;
        else
            node=q.front();
        
        q.pop();
    }
}

template<class T>
void binaryTree<T>::erase(treeNode<T>*node){
    //后序遍历删除，左-右-中
    //显然父节点必须在孩子节点删除后再删除
    if(node!=nullptr){
        this->erase(node->leftChild);
        this->erase(node->rightChild);
        delete node;
    } 
}

template<class T>
int binaryTree<T>::calHeight(treeNode<T>*node){
    if(node==nullptr)
        return 0;
    
    int hl=this->calHeight(node->leftChild);
    int hr=this->calHeight(node->rightChild);

    if(hl>hr)
        return ++hl;
    else
        return ++hr;
}

int main(){
    binaryTree<int>tree;
    int*v=new int;
    
    *v=1;

    treeNode<int>*n1=new treeNode<int>(*v);
    tree.getRoot()=n1;

    *v=2;
    treeNode<int>*n2=new treeNode<int>(*v);
    n1->leftChild=n2;

    *v=3;
    treeNode<int>*n3=new treeNode<int>(*v);
    n1->rightChild=n3;

    *v=4;
    treeNode<int>*n4=new treeNode<int>(*v);
    n2->leftChild=n4;

    *v=5;
    treeNode<int>*n5=new treeNode<int>(*v);
    n3->rightChild=n5;

    cout<<"preOrder:"<<endl;
    tree.preOrder(tree.getRoot());

    cout<<"inOrder:"<<endl;
    tree.inOrder(tree.getRoot());

    cout<<"postOrder:"<<endl;
    tree.postOrder(tree.getRoot());

    cout<<"levelOrder:"<<endl;
    tree.levelOrder(tree.getRoot());

    cout<<"Height is: "<<tree.calHeight(tree.getRoot())<<endl;
    
    tree.erase(tree.getRoot());
    delete v;
	delete n1;
	delete n2;
	delete n3;
	delete n4;
	delete n5;
}